package com.Questions.DP;

/**
 * 爬楼梯
 * n阶楼梯 每次可以爬1个或2 个台阶 有多少种方法可以爬到楼顶
 */
public class leetcode70 {
    // 已有解法是递归 加哈希表存储
    // 现在写动态规划
    // f(x)=f(x-1)+f(x-2)

    // 滚动数组 一种能够在动态规划过程中降低空间复杂度的方法
    // 由于计算f(x)只需要 f(x-1)f(x-2)
    // 所以使用滚动数组
    // 使空间复杂度 降到常数
    // 逆天的 滚动数组思想
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }


}
